Shuffle-exchange network

The order-4 shuffle-exchange network, with its vertices arranged in numerical order

In graph theory, the shuffle-exchange network is an undirected cubic multigraph, whose vertices represent binary sequences of a given length and whose edges represent two operations on these sequence, circular shifts and flipping the lowest-order bit.

Definition

In the version of this network introduced by Tomas Lang and Harold S. Stone in 1976, simplifying earlier work of Stone in 1971, the shuffle-exchange network of order $d$ consisted of an array of $2^{d}$ cells, numbered by the $2^{d}$ different binary numbers that can be represented with $d$ bits. These cells were connected by communications links in two different patterns: "exchange" links in which each cell is connected to the cell numbered with the opposite value in its lowest-order bit, and "shuffle" links in which each cell is connected to the cell whose number is obtained by a circular shift that shifts every bit to the next more significant position, except for the highest-order bit which shifts into the lowest-order position. The "exchange" links are bidirectional, while the "shuffle" links can only transfer information in one direction, from a cell to its circular shift.

Subsequent work on networks with this topology removed the distinction between unidirectional and bidirectional communication links, allowing information to flow in either direction across each link.

Applications

The advantage of this communications pattern, over earlier methods, is that it allows information to be rapidly transferred through a small number of steps from any vertex in the network to any other vertex, while only requiring a single bit of control information (which of the two communications links to use) for each communications step. Fast parallel algorithms for basic problems including sorting, matrix multiplication, polynomial evaluation, and Fourier transforms are known for parallel systems using this network.

Layout area

If this network is given a straightforward layout in the integer lattice, with the vertices placed on a line in numerical order, with each lattice edge carrying part of at most one communication link, and with each vertex or crossing of the network placed at a lattice point, the layout uses area $O(2^{2d})$, quadratic in its number of vertices. However, more compact and asymptotically optimal layouts with area $O(2^{2d}/d^{2})$ were described by F. Thomson Leighton in his 1981 doctoral dissertation.

Related networks

A related communications network, the "omega network" or multi-stage shuffle-exchange network, consists of a given number of stages, each consisting of $2^{d}$ vertices, with the shuffle links connecting pairs of vertices in consecutive stages and the exchange links connecting pairs of vertices in the same stage as each other.

The same operations on binary words, of rotation and flipping the first bit, can also be used to generate the cube-connected cycles, a different cubic parallel communications network with a greater number of vertices. Instead of having the binary words themselves as its vertices, the vertices of the cube-connected cycles represent operations on words that can be generated by rotation and flipping, and the edges represent the composition of one of these operations with an additional rotation or flip.